package com.soul.base.algorithm.level01;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * a06Tree:   A B C D E F G H I J K L M N O
 * A
 * B               C
 * D       E       F       G
 * H   I   J   K   L   M   N   O
 * <p>
 * 前序遍历：ABDH I EJ K CFL M GN O
 * 特点: 根 -> 左子树 -> 右子树
 * <p>
 * 中序遍历: HDI B JEK A LFM C NGO
 * 特点: 左子树 -> 根 -> 右子树
 * <p>
 * 后序遍历: HID JKE B LMF NOG C  A
 * 特点: 左子树 -> 右子树 -> 根
 * <p>
 * 层序遍历: A BC DEFG HIJKLMNO
 * 特点: 根 -> 左 -> 右
 *
 */
public class _06_Tree<T extends Comparable<? super T>> {
    private static class BinaryNode<T> {
        BinaryNode(T theElement) {
            this(theElement, null, null);
        }

        BinaryNode(T theElement, BinaryNode<T> lt, BinaryNode<T> rt) {
            element = theElement;
            left = lt;
            right = rt;
        }

        T element;
        BinaryNode<T> left;
        BinaryNode<T> right;
    }

    private BinaryNode<T> root;

    public void insert(T x) {
        root = insert(x, root);
    }

    public boolean isEmpty() {
        return root == null;
    }

    private BinaryNode<T> insert(T x, BinaryNode<T> t) {
        if (t == null) {
            return new BinaryNode<>(x, null, null);
        }

        int compareResult = x.compareTo(t.element);

        if (compareResult < 0) {
            t.left = insert(x, t.left);
        } else if (compareResult > 0) {
            t.right = insert(x, t.right);
        } else {
            System.out.println("重复数据");
        }

        return t;
    }

    /**
     * 前序遍历
     * 递归
     */
    public void preOrder(BinaryNode<T> node) {
        if (node != null) {
            System.out.print(node.element + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    /**
     * 中序遍历
     * 递归
     */
    public void midOrder(BinaryNode<T> node) {
        if (node != null) {
            midOrder(node.left);
            System.out.print(node.element + " ");
            midOrder(node.right);
        }
    }

    /**
     * 后序遍历
     * 递归
     */
    public void posOrder(BinaryNode<T> node) {
        if (node != null) {
            posOrder(node.left);
            posOrder(node.right);
            System.out.print(node.element + " ");
        }
    }

    /*
     * 层序遍历
     * 递归
     */
    public void levelOrder(BinaryNode<T> node) {
        if (node == null) {
            return;
        }

        int depth = depth(node);

        for (int i = 1; i <= depth; i++) {
            levelOrder(node, i);
        }
    }

    private void levelOrder(BinaryNode<T> node, int level) {
        if (node == null || level < 1) {
            return;
        }

        if (level == 1) {
            System.out.print(node.element + " ");
            return;
        }

        // 左子树
        levelOrder(node.left, level - 1);

        // 右子树
        levelOrder(node.right, level - 1);
    }

    public int depth(BinaryNode<T> node) {
        if (node == null) {
            return 0;
        }

        int l = depth(node.left);
        int r = depth(node.right);
        if (l > r) {
            return l + 1;
        } else {
            return r + 1;
        }
    }

    /**
     * 前序遍历
     * 非递归
     */
    public void preOrder1(BinaryNode<T> node) {
        Stack<BinaryNode> stack = new Stack<>();
        while (node != null || !stack.empty()) {
            while (node != null) {
                System.out.print(node.element + " ");
                stack.push(node);
                node = node.left;
            }
            if (!stack.empty()) {
                node = stack.pop();
                node = node.right;
            }
        }
    }

    /**
     * 中序遍历
     * 非递归
     */
    public void midOrder1(BinaryNode<T> node) {
        Stack<BinaryNode> stack = new Stack<>();
        while (node != null || !stack.empty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.empty()) {
                node = stack.pop();
                System.out.print(node.element + " ");
                node = node.right;
            }
        }
    }

    /**
     * 后序遍历
     * 非递归
     */
    public void posOrder1(BinaryNode<T> node) {
        Stack<BinaryNode> nodeStack = new Stack<>();
        Stack<Integer> flagStack = new Stack<>();
        int isLastLeftPoint = 1;
        int isNotLastLeftPoint = 0;
        while (node != null || !nodeStack.empty()) {
            //压入左节点
            while (node != null) {
                nodeStack.push(node);
                flagStack.push(isNotLastLeftPoint);
                node = node.left;
            }

            //打印最左端点
            while (!nodeStack.empty() && flagStack.peek() == isLastLeftPoint) {
                flagStack.pop();
                System.out.print(nodeStack.pop().element + " ");
            }

            //更换方向(左压入完成->右), 标记左端点
            if (!nodeStack.empty()) {
                flagStack.pop();
                flagStack.push(isLastLeftPoint);
                node = nodeStack.peek();
                node = node.right;
            }
        }
    }

    /*
     * 层序遍历
     * 非递归
     */
    public void levelOrder1(BinaryNode<T> node) {
        if (node == null) {
            return;
        }

        BinaryNode<T> binaryNode;
        Queue<BinaryNode> queue = new LinkedList<>();
        queue.add(node);

        while (queue.size() != 0) {
            binaryNode = queue.poll();

            System.out.print(binaryNode.element + " ");

            if (binaryNode.left != null) {
                queue.offer(binaryNode.left);
            }
            if (binaryNode.right != null) {
                queue.offer(binaryNode.right);
            }
        }
    }

    public static void main(String[] args) {
        /*
            4
          2   6
         1 3 5 7
                8
                 9
         */
        int[] input = {4, 2, 6, 1, 3, 5, 7, 8, 9};
        _06_Tree<Integer> tree = new _06_Tree<>();
        for (int i = 0; i < input.length; i++) {
            tree.insert(input[i]);
        }
        System.out.print("递归前序遍历: \t");
        tree.preOrder(tree.root);
        System.out.print("\n非递归前序遍历: \t");
        tree.preOrder1(tree.root);
        System.out.print("\n递归中序遍历: \t");
        tree.midOrder(tree.root);
        System.out.print("\n非递归中序遍历: \t");
        tree.midOrder1(tree.root);
        System.out.print("\n递归后序遍历: \t");
        tree.posOrder(tree.root);
        System.out.print("\n非递归后序遍历: \t");
        tree.posOrder1(tree.root);
        System.out.print("\n递归层序遍历: \t");
        tree.levelOrder(tree.root);
        System.out.print("\n非递归层序遍历: \t");
        tree.levelOrder1(tree.root);
    }
}